package com.celan.year2023.month01.day21;

import java.util.Arrays;
import java.util.HashMap;

public class Solution {

    public int minSideJumps(int[] obstacles) {
        int n = obstacles.length - 1;
        //创建一维滚动dp数组，分别为3条路
        int[] dp = new int[3];
        //初始化，从0或2赛道开始需要跳一格
        dp[0] = 1;
        dp[2] = 1;
        for (int i = 1; i <= n; i++) {
            //先计算前面的三条路最短侧跳次数
            int min = Integer.MAX_VALUE;
            for (int j = 0; j < 3; j++) {
                if (j == obstacles[i] - 1) {//当前有障碍
                    dp[j] = Integer.MAX_VALUE;
                } else {//当前无障碍，计算之前的最短侧跳次数
                    min = Math.min(min, dp[j]);
                }
            }
            for (int j = 0; j < 3; j++) {
                //当前有障碍，跳过
                if (j == obstacles[i] - 1) continue;
                //当前无障碍，计算当前的最短侧跳次数
                //当前最短侧跳次数=min(不跳直接过来,从上一个地方跳到当前赛道)
                dp[j] = Math.min(dp[j], min + 1);
            }
        }
        return Math.min(dp[0], Math.min(dp[1], dp[2]));
    }

    //[1,0,2]
    public boolean isIdealPermutation(int[] nums) {
        int n = nums.length;
        if (n < 2) return true;
        for (int i = 0; i < n; i++) {
            if (Math.abs(nums[i] - i) > 1) return false;
        }
        return true;
    }

    public boolean validTicTacToe(String[] board) {
        int xCount = 0, oCount = 0;
        for (String row : board) {
            for (char c : row.toCharArray()) {
                if (c == 'X') xCount++;
                if (c == 'O') oCount++;
            }
        }
        //[(X和O个数正确)且(X如果赢了，X就要比O多走一步)]或[O赢了,O走的步数要和X一样多]
        return !((oCount != xCount && oCount != xCount - 1) || (oCount != xCount - 1 && win(board, 'X'))
                || (oCount != xCount && win(board, 'O')));
    }

    public boolean win(String[] board, char p) {
        for (int i = 0; i < 3; ++i) {
            //有列相等
            if ((p == board[0].charAt(i) && p == board[1].charAt(i) && p == board[2].charAt(i)) ||
                    //有行相等
                    (p == board[i].charAt(0) && p == board[i].charAt(1) && p == board[i].charAt(2))) {
                return true;
            }
        }
        //对角线相等
        return ((p == board[0].charAt(0) && p == board[1].charAt(1) && p == board[2].charAt(2)) ||
                (p == board[0].charAt(2) && p == board[1].charAt(1) && p == board[2].charAt(0)));
    }

    public double largestTriangleArea(int[][] points) {
        int n = points.length;
        double ret = 0.0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    ret = Math.max(ret, triangleArea(points[i][0], points[i][1], points[j][0], points[j][1], points[k][0], points[k][1]));
                }
            }
        }
        return ret;
    }

    public double triangleArea(int x1, int y1, int x2, int y2, int x3, int y3) {
        return 0.5 * Math.abs(x1 * y2 + x2 * y3 + x3 * y1 - x1 * y3 - x2 * y1 - x3 * y2);
    }
}
